1. Field of the Invention
The present invention relates to content addressable memories (CAMs), and more particularly, to a CAM having a function for substituting a spare CAM word for a defective CAM word.
2. Description of the Related Art
A CAM is a functional memory in which a search input data is compared with a vast amount of data stored therein at the same time, and the address of a matched word is output.
FIG. 8 is a block diagram showing address selection performed at a read/write access in a conventional CAM.
A CAM 54 shown in FIG. 8 is formed, for example, of a CAM array 56 having 256 CAM words (256 rows), a row decoder 58 for decoding address signals ADR[7:0], and a priority encoder 60 for sequentially encoding the address of a CAM word for which matching has been detected, according to a predetermined priority.
In the CAM 54 shown in FIG. 8, the row decoder 58 selects the CAM word corresponding to the address signals ADR[7:0] externally input, and a read/write access is performed for the stored data. A search operation between search data externally input and stored data stored in each CAM word is performed at the same time, and the priority encoder 60 sequentially outputs the address of a CAM word for which matching has been detected, according to a predetermined priority.
In semiconductor memories such as SRAMs and DRAMs, a redundant-circuit technique has been generally used, in which spare memory words are provided in advance as redundant circuits; if a defective memory word is found, the defective memory word is replaced with a spare memory word; and yield of the semiconductor memories is improved.
In CAMs, however, due to their special functions and circuit structures, such as their column structure largely different from that of usual semiconductor memories, and a function (encoding) for sequentially outputting a matched address according to the priority after searching, in addition to a function (decoding) for selecting an address in a data read/write access, a defective CAM word has hardly been substituted for.
As CAMs have been holding large capacities in these days, the development of CAMs which employ a redundant circuit has been started.
FIG. 9 is a block diagram showing address selection in a CAM which employs a redundant-circuit technique of an address conversion method.
The redundant-circuit technique is applied to a CAM 62 shown in FIG. 9. The CAM 62 is provided, in addition to the components of the CAM 54 shown in FIG. 8, with an FR pre-decoder 64, a logical-to-physical converter 66, a fail row decoder and fail row disable circuit 68, and a physical-to-logical converter 70.
In the CAM 62 shown in FIG. 9, a CAM array 56 has a CAM word R256 as one spare word in addition to usual 256 CAM words, R0, R1, . . . , and R255. The FR pre-decoder 64 stores a signal RD_EB indicating whether a defective CAM word exists, and if there is a defective CAM word, the address signals FA[7:0] of the defective CAM word.
When there is no defective CAM word (signal RD_EB=0), the logical-to-physical converter 66 outputs the address signals ADR[7:0] as they are to the row decoder 58. When a defective CAM word is found (signal RD_EB=1), the address signals ADR[7:0] externally input and the address signals FA[7:0] of the defective CAM word are compared in magnitude.
As shown in FIG. 10A, when ADR[7:0]xe2x89xa7FA[7:0], the address signals ADR[7:0] are incremented by 1 and output to the row decoder 58 as signals P_ADR[8:0]. In other words, memory addresses are shifted downwards by one after the address of the defective CAM word. When ADR[7:0] less than FA[7:0], the address signals ADR[7:0] are output to the row decoder 58 as they are.
The operations of the row decoder 58, the CAM array 56, and the priority encoder 60 is the same as those in the CAM 54 shown in FIG. 8 except that the address signals P_ADR[8:0] are input from the logical-to-physical converter 66 instead of the address signals ADR[7:0] externally input. The fail row decoder and fail row disable circuit 68 disables a detection result of matching or unmatching, output from the defective CAM word.
When there is no defective CAM word (signal RD_EB=0), the physical-to-logical converter 70 outputs address signals P_HHA[7:0] input from the priority encoder 60 as they are. When a defective CAM word is found (signal RD_EB=1), the address signals P_HHA[8:0] input from the priority encoder 60 and the address signals FA[7:0] of the defective CAM word are compared in magnitude.
As shown in FIG. 10B, when P_HHA[8:0]xe2x89xa7FA[7:0], P_HHA[8:0] are reduced by 1 and output as signals HHA[7:0]. In other words, memory addresses are shifted upwards by one after the address of the defective CAM word. When P_HHA[8:0] less than FA[7:0], the address signals P_HHA[7:0] are output as they are as signals HHA[7:0].
In other words, as shown in FIG. 11, in the CAM 62, when a CAM word P3 is defective, for example, the logical-to-physical converter 66 outputs memory addresses L0 to L2 of the address signals ADR externally input, as they are, and shifts memory addresses L3 to L6 downwards by 1. After encoding, the physical-to-logical converter 70 outputs memory addresses P0 to P2 as they are, and shifts memory addresses P4 to P7 upwards by 1.
Therefore, since addresses are increased, if necessary, at the input side (decoder side), and they are reduced contrarily at the output side (encoder side), an external interface can use the CAM 62 without taking a defective CAM word into consideration.
In the CAM 62, which uses the conventional redundant-circuit technique, however, since logical addresses (addresses externally input) and physical addresses (addresses actually used at the inside) are mutually converted by the use of the magnitude comparison circuits, the adder, and the subtracter, its circuit has a large scale and a complicated structure. In addition, the circuit 68 for disabling the match output of a defective CAM word is required. The CAM 62 has a large demerit of an increase in area due to the addition of a redundant circuit.
Further, since a magnitude comparison, an addition, and a subtraction are performed every time a read/write access of stored data and a search operation are performed, an output delay time is increased very much compared with that in the CAM 54, which is not provided with a redundant circuit. Especially, the delay time of the encoding output of a memory address after a match search operation is an important issue related to the specification of the CAM, although the delay time depends on the circuit structures of the magnitude comparison circuits, the adder, and the subtracter.
It is an object of the present invention to provide a content addressable memory (CAM) which solves the problems caused by the conventional technique, which has a spare CAM word as a redundant circuit without increasing a circuit scale and an output delay time, and which can improve a product yield.
The foregoing object is achieved in one aspect of the present invention through the provision of a content addressable memory (CAM) including a plurality of CAM words; one or more spare CAM word serving as a redundant circuit; a defective-CAM-word address storage section for holding information indicating whether there is one or more defective CAM word in the plurality of CAM words, and if there is one or more defective CAM word, address information of the defective CAM word; a shift control circuit for controlling such that the addresses of CAM words located at lower-order addresses than the defective CAM word are shifted in a lower-order direction or in an higher-order direction by the use of the spare CAM word, according to the address information of the defective CAM word, held in the defective-CAM-word address storage section; a first shift circuit for shifting the addresses of CAM words located at lower-order addresses than i-th (i: integer equal to 1 or more) defective CAM word in the lower-order direction by xe2x80x9cixe2x80x9d according to the control of the shift control circuit at a read/write access of data; and a second shift circuit for shifting the addresses of the CAM words located at lower-order addresses than the i-th defective CAM word in the higher-order direction by xe2x80x9cixe2x80x9d according to the control of the shift control circuit at a search operation.
Since an lower order and a higher order are relative to each other, the above content addressable memory may be configured such that xe2x80x9clower orderxe2x80x9d is replaced with xe2x80x9chigher orderxe2x80x9d and xe2x80x9chigher orderxe2x80x9d is replaced with xe2x80x9clower order.xe2x80x9d
The foregoing object may also be achieved by the present invention through the provision of a content addressable memory (CAM) including a plurality of CAM words; one or more spare CAM word serving as a redundant circuit; a defective-CAM-word address storage section for holding information indicating whether there is one or more defective CAM word in the plurality of CAM words, and if there is one or more defective CAM word, address information of the defective CAM word; a first shift control circuit for controlling so as to shift the addresses of the CAM words located at lower-order addresses than the defective CAM word in the lower-order direction by the use of the spare CAM word, according to the address information of the defective CAM word, held in the defective-CAM-word address storage section; a first shift circuit for shifting the addresses of CAM words located at lower-order addresses than i-th (i: integer equal to 1 or more) defective CAM word in the lower-order direction by xe2x80x9cixe2x80x9d according to the control of the first shift control circuit at a read/write access of data; a second shift control circuit for controlling so as to shift the addresses of the CAM words located at lower-order addresses than the defective CAM word in the higher-order direction by the use of the spare CAM word, according to the address information of the defective CAM word, held in the defective-CAM-word address storage section; and a second shift circuit for shifting the addresses of the CAM words located at lower-order addresses than the i-th defective CAM word in the higher-order direction by xe2x80x9cixe2x80x9d according to the control of the second shift control circuit at a search operation.
The above content addressable memory may also be configured such that xe2x80x9clower orderxe2x80x9d is replaced with xe2x80x9chigher orderxe2x80x9d and xe2x80x9chigher orderxe2x80x9d is replaced with xe2x80x9clower order.xe2x80x9d